package com.explorati.LeetCode279.numSquares;

import java.util.Arrays;

/**
 * @ Author : Weijian_Wang
 * @ Date : Created in 13:03 2020/10/7 0007
 * @ Description ：
 */
public class Solution {

    /**
     * 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
     *
     * 输入: n = 12
     * 输出: 3
     * 解释: 12 = 4 + 4 + 4.
     *
     * @param n
     * @return
     */
    public int numSquares(int n) {
        int[] res = new int[n + 1];
        Arrays.fill(res, Integer.MAX_VALUE);
        res[0] = 0;

        //当前求解数 最大能开方的值
        int max_square_index = (int) (Math.sqrt(n) + 1);
        // 完全平方数列表
        int square_nums[] = new int[max_square_index];
        for(int i = 1; i < max_square_index; i++) {
            square_nums[i] = i * i;
        }
        //从 1 开始，遍历到n
        for(int i = 1; i <= n; i ++) {
            // 寻找当前求的数的 最小路径
            for(int j = 1; j < max_square_index; j ++) {
                if(i < square_nums[j]) {
                    break;
                }
                res[i] = Math.min(res[i], res[i - square_nums[j]] + 1);
            }
        }

        return res[n];
    }
}
